#pragma once

#include <vector>
#include <utility>

namespace sorting
{
    namespace impl
    {
        /**
         * @brief   合并左右两个有序数组
         * @note    左子数组边界为[left, mid]，右子数组边界为[mid + 1, right]
         * @tparam  T       基本数据类型
         * @param   vec     基本数据类型数组
         * @param   left    左子数组左边界
         * @param   mid     两有序数组的分界线
         * @param   right   右子数组有边界
         */
        template <typename T>
        void merge(std::vector<T> &vec, std::size_t left, std::size_t mid, std::size_t right)
        {
            using std::size_t;
            using std::vector;

            // 创建临时数组 tmp，用于存放合并后的结果
            vector<T> tmp(right - left + 1);

            // 初始化左右子数组和 tmp 的起始索引
            size_t i = left, j = mid + 1;
            size_t k = 0;

            // 当左右子数组都还有元素时，进行比较并将较小的元素
            // 复制到临时数组 tmp 中
            while (i <= mid && j <= right)
            {
                if (vec[i] <= vec[j])
                {
                    tmp[k] = vec[i];
                    i++;
                }
                else
                {
                    tmp[k] = vec[j];
                    j++;
                }

                k++;
            }

            // 将左右子数组可能的剩余元素复制到临时数组中
            while (i <= mid)
            {
                tmp[k] = vec[i];
                k++;
                i++;
            }

            while (j <= right)
            {
                tmp[k] = vec[j];
                k++;
                j++;
            }

            // 将 tmp 的各元素复制回 vec
            for (size_t i = 0; i < tmp.size(); ++i)
            {
                vec[left + i] = tmp[i];
            }
        }
    } // namespace impl

    /**
     * @brief           归并排序
     * @tparam  T       基本数据类型
     * @param   vec     基本数据类型数组
     * @param   left    数组左边界
     * @param   right   数组右边界
     */
    template <typename T>
    void MergeSort(std::vector<T> &vec, std::size_t left, std::size_t right)
    {
        // 终止条件
        if (left >= right)
        {
            return;
        }

        // 划分阶段
        std::size_t mid = left + (right - left) / 2;
        MergeSort(vec, left, mid);
        MergeSort(vec, mid + 1, right);

        // 合并阶段
        impl::merge(vec, left, mid, right);
    }

    /**
     * @brief           归并排序（便捷版本）
     * @tparam  T       基本数据类型
     * @param   vec     基本数据类型数组
     */
    template <typename T>
    void MergeSort(std::vector<T> &vec)
    {
        const std::size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        MergeSort(vec, 0, len - 1);
    }
} // namespace sorting